Permutacje

Limit pamięci: 32 MB

Permutacja¹ zbioru jest inwolucją wtedy i tylko wtedy, gdy dla każdego .

Wyrażeniem nawiasowym długości będziemy nazywać dowolne słowo długości składające się wyłącznie ze znaków '(' oraz ')'. Wyrażenie nawiasowe jest poprawne, jeśli liczba nawiasów otwierających jest równa liczbie nawiasów zamykających, a w każdym prefiksie tego wyrażenia liczba znaków '(' jest nie mniejsza od liczby znaków ')'.

Powiemy, że permutacja długości koduje wyrażenie nawiasowe o długości , jeśli nawiasy otwierające w wyrażeniu (od lewej do prawej) są na pozycjach , zaś zamykające - także od lewej do prawej - na pozycjach . W szczególności, w takim przypadku zachodzi oraz .

Znamy wartości pewnej permutacji dla niektórych argumentów. Należy stwierdzić, na ile sposobów można określić pozostałe wartości , tak by była ona inwolucją i kodowała poprawne wyrażenie nawiasowe.

Wejście

W pierwszym wierszu standardowego wejścia znajdują się dwie liczby całkowite oraz () oddzielone pojedynczym odstępem. W każdym z kolejnych wierszy znajduje się jedna para liczb całkowitych oddzielonych pojedynczym odstępem; -ty spośród tych wierszy zawiera liczby i (), oddzielone pojedynczym odstępem i oznaczające, że . Wszystkie , jak również wszystkie , są parami różne.

Wyjście

W pierwszym i jedynym wierszu standardowego wyjścia należy wypisać jedną liczbę całkowitą: liczbę permutacji zbioru , które są inwolucjami, kodują poprawne wyrażenie nawiasowe oraz spełniają podane na wejściu równości.

Przykład

Dla danych wejściowych:

3 4
1 1
2 2
4 3
6 6

poprawną odpowiedzią jest:

1

Wyjaśnienie do przykładu: Jedyna permutacja, która spełnia wymogi zadania, to , a koduje ona następujące wyrażenie nawiasowe: (()()).

Autor zadania: Dariusz Leniowski.